package com.shm.leetcode;

/**
 * 486. 预测赢家
 * 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
 *
 * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[1, 5, 2]
 * 输出：False
 * 解释：一开始，玩家1可以从1和2中进行选择。
 * 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
 * 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
 * 因此，玩家 1 永远不会成为赢家，返回 False 。
 * 示例 2：
 *
 * 输入：[1, 5, 233, 7]
 * 输出：True
 * 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
 *      最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
 *
 *
 * 提示：
 *
 * 1 <= 给定的数组长度 <= 20.
 * 数组里所有分数都为非负数且不会大于 10000000 。
 * 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。
 * @author SHM
 */
public class PredictTheWinner {
    int[][] dp = new int[21][21];

    /**
     * 什么是零和博弈? 无论采取何种策略，博弈双方的总得分不变。即一个人得分变多，另一个必然减少。在本题中，双方得分的总和即为 nums 的累加和。
     *
     * 在零和博弈中，让自己最优和让对手最差其实是相同的目标！原因还是那句话，两人的总得分不会变化，自己多了，对手必然减少。
     *
     * 那么不妨先让我们转变一下思路，把问题变为，先手如何让对手的最终得分最少(对手最少就意味着自己的最终得分最大，我好啰嗦啊)。
     *
     * 另外，在零和博弈问题中，一般会存在先手优势和后手劣势：
     *
     * 先手优势：因为先手可以先走，所以可决定后手将要面对的局面。因此，后手虽然也会做出最优解，但是先手可以根据先发的优势，让后手进入最优解最差的局面。
     * 后手劣势：当先手走完后，虽然后手也会成为下一回合的先手，也可以做出最优解，但后手无法选择下一回合的局面。
     * 所以一般零和博弈问题的关键都是要找出如何让后手陷入更差的局面的方法。
     *
     * 上面比较绕，但是看明白之后，基本上常见的零和博弈都能搞定了。
     *
     * 再以本题举个例子：
     *
     * 我们设 optimal(L, R) 为在 nums[L:R] 这种局面上，先手的最优得分。
     * 注意，这里的先手抛开了自己或者对手的概念，先手就是指在这种局面上第一个出手的那个人！
     *
     * 当 L == R 时，因为只有一个数字，显然不需要做抉择了，optimal(L, R) 即为 nums[L]。
     * 当 L < R 时，先手有两种选择：
     *
     * 先手选择 nums[L], 让该回合的后手进入 optimal(L+1, R) 局面。
     * 先手选择 nums[R], 让该回合的后手进入 optimal(L, R-1) 局面。
     * 有没有灵光一闪？这就是先手的优势，他可以决定后手要面临的局面。
     *
     * 后手在下一回合面临 optimal(L+1, R) 或者 optimal(L, R-1) 局面时，虽然都能拿到最高分，但是该回合的先手却可以让对方进入最高分最低的那个局面！这就是后手劣势。
     *
     * 那么最终，第一回合先手的最高得分是多少呢？显然为 optimal(1, nums.size())，假设下标从 1 开始。
     * 那么如何计算 optimal(L, R) 呢？
     *
     * 当 L == R，optimal(L, R) 显然等于 nums[L]。
     * 当 L < R 时，optimal(L, R) = sum(L, R) - min(optimal(L+1, R), optimal(L, R-1))。
     * sum(L, R) 表示 nums[L:R] 的累加和，min() 表示让对手进入最高分最低的那个局面。
     *
     *
     * 设第一回合的先手为 Alice，后手为 Bob。
     *
     * 第一回合：Alice 让 Bob 陷入更差的局面，所以 Alice 选择 4，然 Bob 进入局面[1,2,3]。
     * 第二回合：Bob 让 Alice 陷入更差的局面，所以 Bob 选择 3，然 Bob 进入局面[1,2]。
     * 第三回合：Alice 让 Bob 陷入更差的局面，所以 Alice 选择 2，然 Bob 进入局面[1]。
     * 第四回合：Bob 只能选择 1 。
     * 游戏结束。
     * 在整理清楚计算过程之后，接下来就轮到递归出场啦～
     * 首先来整理递归三要素：
     *
     * 终止条件： L == R; 因为此时可直接获得答案，optimal(L, R) = nums[L]。
     * 递进阶段： 计算optimal(L, R) 依赖的两个子问题： optimal(L+1, R), optimal(L, R-1)。
     * 回归阶段： 利用两个子问题的答案，仅需几次简单的运算便可得到 optimal(L, R) 的答案。
     *
     * 作者：Time-Limit
     * 链接：https://leetcode-cn.com/problems/predict-the-winner/solution/ling-he-bo-yi-ji-yi-hua-0ms-gao-ding-by-time-limit/
     * @param nums
     * @return
     */
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length-1;
//        只要先手的得分不少于总和的二分之一即为胜出。
        return dfs(nums,0,n)*2>=sum(nums,0,n);
    }

    public int sum(int[] nums,int l,int r){
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum+=nums[i];
        }
        return sum;
    }

    public int dfs(int[] nums,int l,int r){
        if (dp[l][r]!=0){
            return dp[l][r];
        }
        if (l==r){
            return dp[l][r]=nums[l];
        }
//        整局游戏的先手的最高得分
        return dp[l][r]=sum(nums,l,r)-Math.min(dfs(nums,l+1,r),dfs(nums,l,r-1));
    }


    /**
     * 你一定会理解为什么数组长度为偶数，先手一定获胜？
     * Lucky
     * 发布于 7 小时前
     * 834
     * 解题思路
     * 如题，为什么呢？随便举一个例子[3,1,9,7,4,5,8,2],这是一个偶数长度，因为和是一定的，所以奇数索引数字[3,9,4,8]+偶数索引数字[1,7,5,2]一定。同时一定会存在谁大谁小，如果相等，题目规定了还是先手获胜！
     * 那么我们可以限制让先手要么都拿奇数索引数字，或者只拿偶数索引数字,这样一定会获胜！（数组索引从1开始算起）
     * 再详细说：
     * A拿3，那么B一定拿的是1或者2，属于偶数阵营，假设是2，那么A再去拿8，假设是1，那么A去拿9，这样一定能保证A拿到的都是奇数索引数字，B是偶数索引数字。同理，A去2能保证A都是偶数索引数字，B是奇数索引数字！
     * @param nums
     * @return
     */
    public boolean PredictTheWinner_2(int[] nums) {
        if(nums.length%2==0){
            return true;
        }
        int len=nums.length;
        int [][]dp=new int[len][len];
        for(int i=0;i<len;i++){
            dp[i][i]=nums[i];
        }
        for(int i=len-2;i>=0;i--){
            for(int j=i+1;j<len;j++){
                dp[i][j]=Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
            }
        }
        return dp[0][len-1]>=0;
    }

    public boolean PredictTheWinner_3(int[] nums) {
        int n = nums.length;
        //dp[i][j]表示玩家1在i到j能拿到的最大分数
        int[][] dp=new int[n][n];
        //数组和
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            //长度为1时
            dp[i][i]=nums[i];
            //长度为2时
            if(i<n-1){
                dp[i][i+1]=Math.max(nums[i],nums[i+1]);
            }
        }
//        for (int j = 0; j < n-1; j++) {
//            dp[j][j+1]=Math.max(nums[j],nums[j+1]);
//        }

        for(int l=3;l<=n;l++){
            for(int i=0;i+l-1<n;i++){
                int j=i+l-1;
                int left=Math.min(dp[i+1][j-1],dp[i+2][j])+nums[i];
                int right=Math.min(dp[i+1][j-1],dp[i][j-2])+nums[j];

                dp[i][j]=Math.max(left,right);
            }
        }

        return 2*dp[0][n-1]>=sum;
    }

    /**
     * 方法二：动态规划
     * 状态定义：dp[i][j] 表示作为先手，在区间 nums[i..j] 里进行选择可以获得的 相对分数。相对分数的意思是：当前自己的选择得分为正，对手的选择得分为负。
     *
     *
     * 方法二：动态规划
     * 方法一使用递归，存在大量重复计算，因此时间复杂度很高。由于存在重复子问题，因此可以使用动态规划降低时间复杂度。
     *
     * 定义二维数组 \textit{dp}dp，其行数和列数都等于数组的长度，\textit{dp}[i][j]dp[i][j] 表示当数组剩下的部分为下标 ii 到下标 jj 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
     *
     * 只有当 i \le ji≤j 时，数组剩下的部分才有意义，因此当 i>ji>j 时，\textit{dp}[i][j]=0dp[i][j]=0。
     *
     * 当 i=ji=j 时，只剩一个数字，当前玩家只能拿取这个数字，因此对于所有 0 \le i < \textit{nums}.\text{length}0≤i<nums.length，都有 \textit{dp}[i][i]=\textit{nums}[i]dp[i][i]=nums[i]。
     *
     * 当 i<ji<j 时，当前玩家可以选择 \textit{nums}[i]nums[i] 或 \textit{nums}[j]nums[j]，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：
     *
     * \textit{dp}[i][j]=\max(\textit{nums}[i] - \textit{dp}[i + 1][j], \textit{nums}[j] - \textit{dp}[i][j - 1])
     * dp[i][j]=max(nums[i]−dp[i+1][j],nums[j]−dp[i][j−1])
     *
     * 最后判断 \textit{dp}[0][\textit{nums}.\text{length}-1]dp[0][nums.length−1] 的值，如果大于或等于 00，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/predict-the-winner/solution/yu-ce-ying-jia-by-leetcode-solution/
     *
     * 相对分数 说成 净胜分 ，语义会更强一些。
     *
     * 甲乙比赛，甲先手面对区间[i...j]时，dp[i][j]表示甲对乙的净胜分。
     *
     * 最终求的就是，甲先手面对区间[0...n-1]时，甲对乙的净胜分dp[0][n-1]是否>=0。
     *
     * 甲先手面对区间[i...j]时，
     *
     * 如果甲拿nums[i]，那么变成乙先手面对区间[i+1...j]，这段区间内乙对甲的净胜分为dp[i+1][j]；那么甲对乙的净胜分就应该是nums[i] - dp[i+1][j]。
     * 如果甲拿nums[j]，同理可得甲对乙的净胜分为是nums[j] - dp[i][j-1]。
     * 以上两种情况二者取大即可。
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/predict-the-winner/solution/ji-yi-hua-di-gui-dong-tai-gui-hua-java-by-liweiwei/
     * @param nums
     * @return
     */
    public boolean PredictTheWinner_4(int[] nums) {
        int n = nums.length;
        int[][] dp=new int[n][n];
        // dp[i][j]：作为先手，在区间 nums[i..j] 里进行选择可以获得的相对分数
        for (int i = 0; i < n; i++) {
            dp[i][i]=nums[i];
        }

        // 状态转移方程：dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
        for (int i = n-2; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                dp[i][j]=Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
            }
        }

        return dp[0][n-1]>=0;
    }
}
